package linkList1;

import sun.awt.image.ImageWatched;

public class MyLinkList {

    //链表是由一个个节点组成的，所以定义出节点类
    static  class Node{
        //储存数据的整形成员变量
        int val;
        //每个节点都可储存其他节点的引用
        Node next=null;
        //给节点定义一个带一个参数的构造方法用于初始化val数值成员变量
        //由于我们在实例化节点时不知道下一个节点具体是哪一个
        //所以我们的构造方法就无法对next成员变量进行初始化
        public Node(int val) {
            this.val = val;
        }
    }


    //给链表定义一个头节点head
    Node head=null;


    ////////链表基本方法功能实现//////

    //头插法
    public void addFirst(int data){
        //实例化一个节点
        Node newNode=new Node(data);
        newNode.next=head;
        head=newNode;
    }
    //尾插法
    public void addLast(int data){
        //实例化一个节点
        Node newNode=new Node(data);
        //找到链表的最后一个节点
        Node cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        //此时cur已经是当前节点的最后一个节点
        //将最后一个节点的next引用新的节点
        cur.next=newNode;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        //第一步判断下标位置合法性
        if(index<0||index>size()){
            throw new MyLinkListIndexOutException("下标不合法");
        }
        //判断是否为头插法
        if(index==0){addFirst(data);return;}
        //同理判断是否为尾插法
        if(index==size()){addLast(data);return;}
        //既不是头插也不是尾插的情况
        Node cur=head;
        //实例化一个节点
        Node newNode=new Node(data);
        //因为链表不能记录前面的节点。一旦经过就不能知道前一个节点是谁了
        //所以要在index下标插入新节点，要想达到即连接前节点又达到后一个节点
        //那就需要找到指定下标的前一个元素
        while(index-1>0){
            cur=cur.next;
            index--;
        }
        //此时cur已经找到了index下标的前一个节点
        newNode.next=cur.next;
        cur.next=newNode;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            return false;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (head == null) {
            System.out.println("链表为空无法删除");
            return;
        }
        Node cur = head;
        while(cur!=null){
            Node curNext=cur.next;
            //判断是否为头节点
            if(cur==head&&cur.val==key){
                head=head.next;
                return;
            }
            if(curNext.val==key){
                cur.next=curNext.next;
                return;
            }
            cur=curNext;
            curNext=curNext.next;
        }
    }
    //得到单链表的长度
    public int size(){
        int count=0;
        Node cur=head;
        while(cur!=null){
           count++;
            cur=cur.next;
        }
        return count;
    }
    //打印链表
    public void display(){
        Node cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //清除链表数据
    public void clear(){
        if(head==null){return;}
        Node cur=head;
        Node curNext=head.next;
        while(curNext!=null){
            cur.next=null;
            cur=curNext;
            curNext=curNext.next;
        }
        head=null;
    }

    ///////常见面试题////////
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head==null)return;
        //先判断除头节点外的节点是否为要删除的元素，最后在
        //对头节点进行判断，这样子可以避免先从头节点开始判断(要写循环)
        Node cur=head;
        Node curNext=head.next;
        while(curNext!=null){
            if(curNext.val==key){
                cur.next=curNext.next;
                curNext=curNext.next;
                continue;
            }
            cur=curNext;
            curNext=curNext.next;
        }
        if(head.val==key){
            head=head.next;
        }
    }
}
